1. Field of the Invention
This invention relates generally to Reed-Solomon encoders. More particularly, it relates to a Multi-Rate Reed-Solomon encoder.
2. Background
Reed-Solomon codes are block-based error correcting codes with a wide range of applications in digital communications and storage. Reed-Solomon codes are used to correct errors in many systems including storage devices (including tape, Compact Disk, DVD, barcodes, etc), wireless or mobile communications (including cellular telephones, microwave links, etc), satellite communications, digital television/DVB, high-speed modems such as ADSL, xDSL, etc.
A Reed-Solomon encoder takes as input a block of digital data, comprising a sequence of digital information bits, and interprets it as a sequence of information symbols. Each such symbol comprises m bits of the digital information sequence. The block of input data comprises k such information symbols. The Reed-Solomon encoder produces p additional redundant symbols, which are concatenated with the k information symbols to form a codeword comprising n=k+p symbols. The parameters of the Reed-Solomon code are indicated by referring to such a code as an RS(n,k) code with m bit symbols.
Errors occur during transmission or storage for a number of reasons (for example noise or interference, scratches on a CD, etc). A Reed-Solomon decoder processes each block and attempts to correct errors and recover the original data. The number and type of errors that can be corrected depends on the characteristics of the Reed-Solomon code. In general, an RS(n,k) decoder can correct any combination of p/2 corrupted symbols provided that the remainder of the n symbols of the codeword are correct.
For instance, a Reed-Solomon encoder may include one popular Reed-Solomon code: RS(255,223) with 8-bit symbols. With this code, each codeword contains 255 code word bytes, of which 223 bytes are data and 32 bytes are parity. In this example, a matching Reed-Solomon decoder can automatically correct up to 16 byte errors anywhere in the codeword.
Reed-Solomon codes are based on a specialist area of mathematics known as abstract algebra, which includes the theory of finite fields, which are also known as Galois fields. A finite field has the property that arithmetic operations (add, multiply, divide, exponentiate, etc.) on field elements always have a result in the field. A Reed-Solomon encoder or decoder needs to carry out these arithmetic operations. Reed-Solomon encoding (and/or decoding) can be carried out in software or in special purpose hardware.
A Reed-Solomon codeword is produced by utilizing polynomial division using the arithmetic of the Galois field. All valid codewords are exactly divisible by the generator polynomial.
The general form of the generator polynomial of a Reed-Solomon code is:
g(x)=(xxe2x88x92xcex1j)(x+xcex1j+1) . . . (xxe2x88x92xcex1j+pxe2x88x921)
where j is an arbitrary integer, xcex1 is a special element of the Galois field referred to as a primitive element, and p is the number of redundant symbols to be produced. The input to the encoder is the sequence of information symbols
{u0, u1, . . . , ukxe2x88x921}
which is interpreted as the polynomial
u(x)=u0xkxe2x88x921+u1xkxe2x88x922+. . . +ukxe2x88x922x+ukxe2x88x921
A polynomial division using the Galois field arithmetic processes this polynomial and the generator polynomial to produce a quotient polynomial q(x) and a remainder polynomial r(x) satisfying
xpu(x)=q(x)g(x)+r(x),
where
r(x)=r0xpxe2x88x921+r1xpxe2x88x922+. . . +rpxe2x88x922x+rpxe2x88x921 
The codeword is formed by appending the p redundant symbols to the information symbols, forming the codeword sequence:
{c0, c1, . . . , cnxe2x88x921}={u0, u1, . . . ukxe2x88x921, r0, r1, . . . , rpxe2x88x921}
This sequence has the property that the polynomial:
c(x)=c0xnxe2x88x921+c1xnxe2x88x922+ . . . +cnxe2x88x922x+cnxe2x88x921
is divisible by the generator polynomial g(x).
An example generator polynomial for a Reed-Solomon code RS(255,249) is:
g(x)=(xxe2x88x92xcex10)(xxe2x88x92xcex11)(xxe2x88x92xcex12)(xxe2x88x92xcex13)(xxe2x88x92xcex14)(xxe2x88x92xcex15)
Using the Galois field arithmetic, the terms of this polynomial are multiplied to form the polynomial:
g(x)=x6=g5x5+g4x4+g3x3+g2x2+g1x+g0
where g0, g1, . . . , g5 are specific symbols in the field.
U.S. Pat. No. 5,444,719 to Cox et al., entitled xe2x80x9cAdjustable Error-Correction Composite Reed-Solomon Encoder/Syndrome Generatorxe2x80x9d (hereinafter xe2x80x9cCoxxe2x80x9d), discloses a conventional combined Reed-Solomon encoder/syndrome generator.
FIG. 1 of the present application shows a block diagram of relevant portions of a conventional Reed-Solomon encoder/syndrome generator disclosed, e.g., in FIG. 2 of Cox.
In particular, as shown herein in FIG. 1, the large circles labeled with generator coefficients gi 110-116 represent constant multipliers over a Galois field. These generator coefficient multipliers gi 110-116 tend to dominate the critical net loading, gate count and routing area of a Reed-Solomon encoder. Galois field adders 122-126 each consist of m XOR gates.
The conventional Reed-Solomon encoder shown herein in FIG. 1 is well-known in the art. An advantage of this conventional encoder is that for a judicious choice of j0, the generator coefficients are symmetric, in that
g0=gp=1,
g1=gpxe2x88x921,
g2=gpxe2x88x922, and so on.
In particular, if p is odd, then the generator is symmetric if:   j  =            2      m        -    1    -                  p        -        1            2      
and, if p is even, then the generator is symmetric if:   j  =            2              m        -        1              -          p      2      
If the generator is symmetric, the architecture of FIG. 1 can be implemented with only [p/2] Galois field multipliers, resulting in a simpler implementation than if the generator is not symmetrical. However, a disadvantage of the conventional architecture, e.g., as shown in FIG. 1, is that it does not lend itself easily to supporting more than one specific Reed-Solomon code. This is because the generator coefficients mostly change when a differing number of redundant bytes are to be produced for each of the different Reed-Solomon codes.
The digital filter H(D) 100 of the Reed-Solomon encoder shown in FIG. 1 has a transfer function of the form:             H      ⁡              (        D        )              =                            Y          ⁡                      (            D            )                                    X          ⁡                      (            D            )                              =                        1          +                      1                                          ∑                                  i                  =                  0                                p                            ⁢                              xe2x80x83                            ⁢                                                g                  i                                ⁢                                  D                                      p                    -                    i                                                                                      =                  1          +                                    ∏                              i                =                0                                            p                -                1                                      ⁢                          xe2x80x83                        ⁢                                          H                i                            ⁡                              (                D                )                                                          ,
where             H      i        ⁡          (      D      )        =      1          1      +                        α                      i            +            j                          ⁢        D            
Cox discloses how to produce a Reed-Solomon encoder by cascading p filters with transfer functions of the form Hi(D) as described above, where i=0, 1, . . . , pxe2x88x921.
One advantage of the implementation disclosed by Cox is that each of the filters Hi(D) can also be used independently to produce the decoder syndrome Si used in a complementary Reed-Solomon decoder. Cox uses the p filters Hi(D) in cascade to perform the Reed-Solomon encoding function, and in parallel to perform the first step of Reed-Solomon decoding. This reduces the amount of hardware required in an implementation utilizing a Reed-Solomon encoder and decoder in the same integrated circuit chip.
Perhaps the most distinctive feature of Cox""s Reed-Solomon encoder is that it implements individual degree polynomial filters. In particular, Cox teaches the use n subfilters, each of degree 1, which are cascaded to produce an encoder transfer function. Cox teaches that these n subfilters can also be used as syndrome calculators. Cox""s individual stages of the cascaded filter can be easily disabled, providing for the ability to produce varying amounts of redundancy from the same basic circuit.
However, a disadvantage of Reed-Solomon encoders such as are disclosed by Cox is that the critical path of the Reed-Solomon encoder can be quite long for large values of p. A second disadvantage of the Cox et al. Reed-Solomon encoder is that it fails to reduce the number of Galois field multipliers beyond that which is achieved in the case where the generator polynomial is symmetrical.
There is a need for a Reed-Solomon encoder which is capable of a reduced number of Galois field multipliers, whether or not the generator polynomial is symmetrical, and which is capable of performing any of a plurality of encoding rates.
In accordance with the principles of the present invention, a multi-rate Reed-Solomon coding device comprises a plurality of multiple degree subfilters. The plurality is less than a maximum number of bytes of redundancy provided by the Reed-Solomon coding device.
A method of providing multiple Reed-Solomon codes in a single coding device in accordance with another aspect of the present invention comprises, for each Reed-Solomon code, grouping a plurality of subfilters into a multiple degree polynomial subfilter. Each grouped plurality of multiple degree polynomial subfilters are optionally cascaded.